% 10-30 páginas

\newcommand{\din}[0]{\ensuremath{\delta_{in}}}
\newcommand{\dout}[0]{\ensuremath{\delta_{out}}}
\newcommand{\gin}[0]{\ensuremath{\mathrm{g}_{in}}}
\newcommand{\gout}[0]{\ensuremath{\mathrm{g}_{out}}}

\chapter{Redes Complexas} \label{cap:redes} 

\begin{section}{Introdução} \label{sec:redes-complexas} % Rodrigo: tá muito seco!

% Mais recentemente, grafos têm sido objeto de estudo de um ramo da física estatística denominado teoria das redes complexas. Este capítulo descreve alguns avanços dessa teoria que são relevantes para este trabalho.

A teoria das redes complexas estuda propriedades gerais de diversos tipos de redes, representadas como grafos, com o uso de ferramentas estatísticas. Estudos realizados na última década revelaram similaridades entre redes estudadas em diversos domínios. Exemplos incluem redes tecnológicas, como a Web e a rede de distribuição de energia elétrica dos Estados Unidos, redes biológicas, como cadeias alimentares e redes de ligações entre proteínas, e redes sociais, como as relações de amizade entre alunos de uma escola \cite{Newman2003}.

O termo ``rede'' em geral está associado a entidades reais, como pessoas e relacionamentos de amizade, enquanto o termo ``grafo'' designa uma abstração matemática conveniente para representar relacionamentos entre objetos. Na teoria das redes complexas, no entanto, os termos são frequentemente usados como sinônimos, e é desta forma que eles são usados neste trabalho.
\end{section}

\begin{section}{Definições Básicas}
	
	Uma rede ou grafo é um conjunto de \emph{vértices} e \emph{arestas}, no qual as arestas relacionam dois vértices. Pode-se dizer também que as arestas ligam ou conectam dois vértices. Uma rede pode ser \emph{orientada} ou \emph{não-orientada}. 
	
	Nas redes orientadas, as arestas (chamadas de arestas orientadas) estabelecem uma relação assimétrica entre dois vértices, um dos quais é dito vértice de origem e o outro, vértice de destino da aresta. Duas arestas são ditas \emph{opostas} se ligam o mesmo par de vértices, porém com origem e destino invertidos. 
	
	Em uma rede orientada, o \emph{grau de saída} de um vértice $x$, denotado $\mathrm{g}_\mathrm{out}(x)$, é o número de arestas com origem no vértice $x$. O \emph{grau de entrada} de um vértice $x$, denotado $\mathrm{g}_\mathrm{in}(x)$, é o número de arestas com destino no vértice $x$. O \emph{grau total} de um vértice $x$ é igual à soma do seu grau de entrada com o seu grau de saída.
	
	Nas redes não-orientadas, a relação entre pares de vértices é simétrica: cada aresta (chamada de aresta não-orientada) liga dois vértices, e não existe distinção entre origem e destino. Em uma rede não-orientada, o \emph{grau} de um vértice $x$, denotado $\mathrm{g}(x)$, é o número de arestas que se relaciona com $x$. Para transformar uma rede não-orientada em uma rede orientada, basta transformar cada aresta não-orientada em duas arestas orientadas opostas que ligam o mesmo par de vértices que a aresta não-orientada. 
	
	Nas redes organizadas em módulos (que podem ser orientadas ou não-orientadas), o conjunto de vértices é particionado em subconjuntos denominados \emph{módulos}. As arestas podem ser classificadas em \emph{internas} (quando ligam vértices pertencentes ao mesmo módulo) ou \emph{externas} (quando ligam vértices pertencentes a módulos distintos).
	
	As redes podem ser representadas graficamente por diagramas com círculos e linhas. Cada vértice é representado por um círculo. Nas redes orientadas, as arestas são representadas por setas que ligam o vértice de origem ao vértice de destino. Duas arestas opostas podem ser representadas de forma simplificada por uma seta que aponta simultaneamente para dois vértices. Nas redes não-orientadas, as arestas são representadas por linhas que conectam dois vértices (sem seta). Os módulos, quando existem, são representados por retângulos ou formas livres que circundam os vértices que contêm.

\end{section}

\begin{section}{Propriedades Estatísticas}
	
Barabási e Albert \cite{Barabasi1999} analisaram uma amostra da \emph{World Wide Web}, modelada como um grafo não-orientado no qual os vértices representam páginas e as arestas representam \emph{links} entre duas páginas. Eles observaram a distribuição dos graus dos vértices, isto é, o número de vértices conectados a outros $k$ vértices ($N(k)$), para cada valor de $k > 0$, e encontraram uma lei de potência, isto é, acharam $N(k)$ proporcional a $k^{-\gamma}$, como mostra a Figura \ref{fig:leidepotencia}. Desde então, leis de potência têm sido encontradas na distribuição de graus de redes estudadas em diversos domínios, inclusive no domínio de software, com $\gamma$ variando tipicamente entre 2 e 3. Redes com esse padrão são chamadas de \emph{redes livres de escala}.

% Eles perceberam que o número de vértices com grau $k$, isto é, vértices ligados a outros $k$ vértices, era aproximadamente proporcional a $k^{-\gamma}$, função conhecida como lei de potência (veja a Figura \ref{fig:leidepotencia}). Desde então, esse padrão de conectividade tem sido encontrado em redes estudadas em diversos domínios, inclusive no domínio de software. Redes com esse padrão são chamadas de redes \emph{livres de escala}.

% Explicar que não há valor característico para o grau de um vértice, e daí vem o nome.

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{figuras/leidepotencia}
	\caption{Distribuição do número de arestas por vértice do tipo lei de potência. Adaptado de \cite{Barabasi2007}.}
	\label{fig:leidepotencia}
\end{figure}

% No caso de redes orientadas, há duas distribuições a serem consideradas: a distribuição dos graus de entrada e a distribuição dos graus de saída. Nas redes orientadas que são livres de escala, ambas as distribuições seguem leis de potência.

% e alto coeficiente de clustering

Se diversas redes possuem um mesmo padrão de distribuição de graus, o que as diferencia? Milo e outros pesquisadores \cite{Milo2002} estudaram a estrutura de redes orientadas de diversos domínios em busca da resposta. Para isso, eles listaram 13 possíveis configurações de arestas em redes com 3 vértices --- as chamadas tríades ---, mostradas na Figura \ref{fig:triades}. Contando o número de vezes que cada tríade aparece em uma rede, é possível formar um vetor, denominado \emph{perfil de concentração de tríades} (PCT), que é característico de redes de um domínio. 

O papel dos PCTs na caracterização de domínios de redes é ilustrado nas Figuras \ref{fig:tcp}(a) e \ref{fig:tcp}(b). Na Figura \ref{fig:tcp}(a), são apresentados PCTs de redes de dois domínios distintos: uma rede de software e uma rede linguística. Na Figura \ref{fig:tcp}(b), são apresentados PCTs de duas redes do mesmo domínio, o domínio de software. Uma análise informal dos gráficos revela que a similaridade entre os PCTs é maior no segundo caso, no qual as redes são do mesmo domínio. No primeiro caso, é notável a diferença nas concentrações das duas primeiras tríades (de cima para baixo). 
% 

\begin{figure}[htbp]
	\centering
		\includegraphics[scale=1]{figuras/triads}
	\caption{Tríades, ou grafos com três vértices, numeradas de 1 a 13.}
	\label{fig:triades}
\end{figure}

\begin{figure}[htbp]
	\centering
		\includegraphics[width=1\textwidth]{figuras/tcp}
	\caption{Comparação entre perfis de concentração de tríades de três redes distintas, extraídos pelo autor através da ferramenta igraph \cite{igraph}. (a) À esquerda, rede de dependências entre as classes do programa JabRef, versão 2.5b2; à direita, rede de adjacências entre palavras da língua japonesa \cite{Milo2004}. (b) À esquerda, a rede do programa JabRef, versão 2.5b2; à direita, a rede do programa ArgoUML, versão 0.28.}
	\label{fig:tcp}
\end{figure}

A similaridade entre PCTs pode ser quantificada através do coeficiente de correlação de Pearson entre os PCTs \cite{Milo2004}. O resultado é um valor entre -1,0 (menor similaridade) e 1,0 (maior similaridade). Na Figura \ref{fig:tcp}(a), o coeficiente de correlação vale $0,68$; na Figura \ref{fig:tcp}(b), $0,98$. Os números confirmam a análise informal da Figura \ref{fig:tcp} e mostram que, no exemplo, a correlação é maior no caso em que as redes pertencem ao mesmo domínio.

Cabe aqui uma ressalva: os PCTs em geral não apresentam um conjunto de valores que seguem a distribuição normal, o que é um pré-requisito para se aplicar a correlação de Pearson. Curiosamente, não foi encontrado nenhum trabalho na literatura que chamasse atenção para esse ponto, tampouco que propusesse alternativas à correlação de Pearson.

% 
% 
% Vale notar que o coeficiente de correlação neste caso não possui significado estatístico. Ainda assim, ele tem sido usado de forma bem sucedida na pesquisa de Milo. % TODO ??? (marco túlio)
% 
% A métrica de similaridade entre PCTs \cite{Milo2004} pode ser interpretada como uma métrica de similaridade entre redes. Sejam $a$ e $b$ duas redes, PCT($x$) o vetor com as concentrações das tríades na rede $x$ e cor($x, y$) o coeficiente de correlação de Pearson entre dois vetores. A similaridade entre as redes, sim($a$, $b$), é dada por
% 
% $$
% \mathrm{sim}(a, b) ~=~ 
%   \mathrm{cor}(\mathrm{PCT}(a), \mathrm{PCT}(b))\mathrm{.}
% $$

\end{section}

\begin{section}{Redes de Dependências no Domínio de Software}

	Redes são muito usadas no domínio de engenharia de software para representar as dependências entre entidades do código-fonte, tais como classes em linguagens orientadas a objetos. 
	%
	Estudos recentes têm aplicado a teoria das redes complexas a redes de software, isto é, redes de dependências entre entidades do código-fonte de sistemas de software. Um dos principais resultados é a constatação de que redes de software são livres de escala, isto é, as dependências entre as entidades da implementação dos sistemas de software se distribuem de acordo com uma lei de potência.
	
	Valverde e Solé \cite{Valverde2003} estudaram redes não-orientadas formadas por relações de agregação de tipos em diagramas UML, programas em C e programas em C++. Myers \cite{Myers2003} analisou redes de chamadas de função em programas em C e redes de agregação e herança em programas em C++. Em ambos os casos as redes foram identificadas como livres de escala. 

	Redes livres de escala também foram encontradas em programas escritos em Smalltalk \cite{Marchesi2004,Concas2007} e em Java \cite{Hyland-Wood2006,Baxter2006,Ichii2008}, em dependências entre pacotes de software \cite{Labelle2004}, em dependências entre bibliotecas dinâmicas \cite{Louridas2008} e até mesmo em referências entre objetos em tempo de execução \cite{Potanin2005}.
\end{section}

\begin{section}{Modelos de Geração de Redes}
% deu 7 páginas
% Organizadas em Módulos

Para tentar explicar os mecanismos responsáveis pela formação de redes livres de escala, vários modelos de redes livres de escala foram propostos. Os modelos são algoritmos que geram vértices e arestas de forma probabilística porém de acordo com certas regras que garantem que, quando o número de vértices tende a infinito, a distribuição dos graus dos vértices tende a uma lei de potência. Tais modelos, portanto, geram redes similares a redes de software, ao menos quanto à distribuição dos graus.

A seguir são apresentados quatro modelos de redes. Os dois primeiros, o de Erdős–Rényi (ER) \cite{Erdos1959} e o de Barabási-Albert (BA) \cite{Barabasi1999}, geram redes sem módulos. Eles foram selecionados devido a sua importância histórica. Os dois últimos, o modelo CGW \cite{Chen2008} e o modelo LFR \cite{Lancichinetti2008,Lancichinetti2009}, foram selecionados por gerarem redes organizadas em módulos. Acredita-se que tal característica os aproxima do processo de construção de sistemas de software, no qual o conceito de módulo desempenha um papel importante.

%, e são apresentados aqui a fim de ilustrar conceitos usados nos outros modelos.


% Assim como um sistema de software é organizado conceitualmente em módulos, uma rede de software deve representar suas entidades organizadas em módulos. A maioria dos modelos de redes livres de escala, no entanto, gera redes sem qualquer tipo de organização hierárquica.
% 
% Após uma pesquisa extensa, embora não-sistemática, realizada durante o primeiro semestre de 2009, foram encontrados dois modelos de redes livres de escala organizadas em módulos: o modelo CGW \cite{Chen2008} e o modelo LFR \cite{Lancichinetti2008,Lancichinetti2009}. Um terceiro modelo, o BCR+, elaborado no contexto deste trabalho, é descrito no próximo capítulo.

 
% Modelo de Erdos-Renyi?
% Modelo de configuração?
% Modelo de Albert-Barabasi?

\begin{subsection}{O modelo de Erdős–Rényi (ER)}
	O modelo de Erdős–Rényi (ER) \cite{Erdos1959} precedeu a teoria das redes complexas. Ele gera redes não-orientadas que, em geral, não são livres de escala. A distribuição esperada dos graus dos vértices é a distribuição de Poisson. O modelo ER recebe dois parâmetros:
	
	\begin{itemize}
		\item $n$, o número de vértices;
		\item $m$, o número de arestas.
	\end{itemize}
	
	Uma rede não-orientada com $n$ vértices pode conter até $\frac{n(n-1)}{2}$ arestas. Nas redes geradas pelo modelo ER, $m$ arestas são selecionadas aleatoriamente dentre as arestas potenciais. Cada aresta potencial tem a mesma probabilidade de ser selecionada.
	
	Nada impede que o modelo seja usado para gerar redes orientadas. Na variedade orientada do modelo ER, considera-se que uma rede com $n$ vértices pode conter até $n(n-1)$ arestas orientadas, e desse conjunto são selecionadas as $m$ arestas.
	
	Pela descrição do modelo, percebe-se que ele pode gerar qualquer rede possível, com qualquer distribuição de graus. A probabilidade de uma rede gerada pelo modelo ER ser livre de escala é, no entanto, baixíssima.

\end{subsection}

\begin{subsection}{O modelo de Barabási-Albert (BA)}	
	
	O modelo de Barabási-Albert (BA) \cite{Barabasi1999} foi o primeiro modelo livre de escala da teoria das redes complexas. Ele gera redes não-orientadas, livres de escala e sem módulos através de dois mecanismos: crescimento e ligação preferencial. Crescimento significa que as redes são construídas a partir da adição sucessiva de novos vértices. Ligação preferencial significa que os vértices com mais arestas apresentam maior probabilidade de receber novas arestas.
	
	O modelo BA aceita os seguinte parâmetros:
	
	\begin{itemize}
		\item $n$, o número de vértices da rede final;
		\item $m$, o número de arestas adicionadas a cada passo.
	\end{itemize}
	
	A rede é inicializada com um número arbitrário de vértices e arestas de forma que cada vértice possua grau maior ou igual a 1. A cada passo, é adicionado um novo vértice, que é ligado através de $m$ novas arestas a $m$ vértices pré-existentes. Os $m$ vértices são escolhidos de acordo com os seus graus, o que significa que a probabilidade de um vértice $x$ ser escolhido, $\mathrm{P}(x)$, é proporcional ao grau de $x$: $\mathrm{P}(x) \sim \mathrm{g}(x)$. Como a soma dos probabilidades dos vértices deve ser igual a 1, a probabilidade de cada vértice é igual ao seu grau dividido pela soma dos graus de todos os vértices da rede:
	
	$$
	\mathrm{P}(x) ~=~ \frac{\mathrm{g}(x)}{\sum_y \mathrm{g}(y)}.
	$$
	
	Diz-se que os novos vértices se ligam \emph{preferencialmente} a vértices com alto grau. Como consequência, alguns poucos vértices acumulam muitas arestas, enquanto a maioria dos vértices permanece com poucas arestas. O processo é repetido até que a rede atinja $n$ vértices.
	
	% IMPORTANTE %% A Figura XXX exemplifica o mecanismo de ligação preferencial.
	
	% MELHOR DEIXAR ISSO DE FORA: Várias adaptações já foram propostas para o modelo BA. Uma adaptação simples pode ser realizada para que o modelo gere redes orientadas. No caso de redes orientadas, as $m$ arestas orientadas adicionadas a cada passo possuem origem no novo vértice. O mecanismo de ligação preferencial pode levar em conta os graus totais dos vértices, $\mathrm{g}(x)$, ou apenas os graus de entrada, $\gin(x)$.

\end{subsection}

\begin{subsection}{O modelo CGW}

O modelo CGW \cite{Chen2008} gera redes orientadas, livres de escala e organizadas em módulos. Baseado no modelo BA, ele utiliza os mecanismos de crescimento e ligação preferencial. Ele foi proposto como um modelo da evolução de sistemas de software. O modelo aceita 11 parâmetros:

\begin{itemize}
\item número de vértices, $n$;
\item número de módulos, $m$;
\item quatro probabilidades, $p_1, p_2, p_3, p_4$, com $p_1 + p_2 + p_3 + p_4 = 1$ e $p_1 > 0$;
\item quatro números naturais, $e_1, e_2, e_3, e_4$;
\item uma constante, $\alpha$, com $\alpha \ge -1$.
\end{itemize}

Nesse modelo, a construção inicia-se com uma rede inicial arbitrária e então vai crescendo de acordo com determinadas regras de formação, até alcançar $n$ vértices. Cada vértice é atribuído a exatamente um dos $m$ módulos no momento em que é criado.

A rede inicial é alterada pela aplicação sucessiva de quatro regras em ordem aleatória:

\begin{itemize}
	
	\item Regra 1: com probabilidade $p_1$, um novo vértice é adicionado a um módulo escolhido aleatoriamente, juntamente com $e_1$ arestas com origem no novo vértice. Os vértices de destino das $e_1$ arestas são escolhidos de acordo com a probabilidade preferencial baseada em módulos (PPBM), explicada mais à frente.
	
	\item Regra 2: com probabilidade $p_2$, são adicionadas $e_2$ arestas. Para cada aresta, o vértice de origem é escolhido aleatoriamente, enquanto o vértice de destino é escolhido de acordo com a PPBM.
	
	\item Regra 3: com probabilidade $p_3$, $e_3$ arestas são religadas. O procedimento de religamento de arestas é descrito a seguir:
	
	\begin{enumerate}
		\item um vértice, $v_1$ é escolhido aleatoriamente;
		\item uma aresta, $a_1$, escolhida aleatoriamente dentre as arestas com origem em $v_1$, é removida da rede;
		\item é adicionada uma nova aresta cuja origem é $v_1$ e o vértice de destino é escolhido de acordo com a PPBM;
	\end{enumerate}
	
	\item Regra 4: com probabilidade $p_4$, $e_4$ arestas escolhidas aleatoriamente são removidas da rede.
	
\end{itemize}

Naturalmente, as probabilidades $p_1, p_2, p_3$ e $p_4$ devem somar 1. Além disso, $p_1$ deve ser maior que zero --- do contrário o número de vértices na rede permanece constante. As quantidades $e_1, e_2, e_3, $ e $e_4$ são inteiros maiores ou iguais a zero.

A probabilidade preferencial baseada em módulos, $\Pi(v_2|v_1)$, é uma função que indica a probabilidade de se escolher um vértice, $v_2$, como destino de uma aresta cujo vértice de origem, $v_1$, já foi determinado. O propósito da PPBM é controlar a proporção de arestas externas na rede, privilegiando a escolha de um vértice de destino pertencente ao mesmo módulo do vértice de origem. Eis a definição da probabilidade preferencial baseada em módulos:

$$
\Pi (v_2|v_1) ~=~
\left\{
\begin{array}{cl}
\dfrac{1 + \mathrm{g}(v_2) \cdot (1 + \alpha)}{Q(v_1)}\mbox{,} 
  & \mbox{se $v_2$ está no mesmo módulo de $v_1$;} \vspace{0.5em} \\ 
\dfrac{1 + \mathrm{g}(v_2)}{Q(v_1)}\mbox{,}
  & \mbox{caso contrário.}
\end{array}
\right.
$$

A seguir é explicado o significado de $\alpha$, g($v$) e Q($v$).

 O parâmetro $\alpha$ controla a proporção de arestas externas na rede. Para $\alpha = -1$, a maioria das arestas serão externas. Para $\alpha > 0$, a maioria das arestas serão internas, e quanto maior o valor de $\alpha$, maior a tendência. Quando $\alpha = 0$, arestas internas e externas são igualmente prováveis.

A expressão g($v$) designa o grau de saída do vértice $v$. O termo $Q$ é apenas uma constante de proporcionalidade cujo propósito é fazer a soma das probabilidades ser igual a 1, e é definido da seguinte forma:

$$
Q(v_1) = \sum_{v \in m(v_1)} (1 + \mathrm{g}(v) \cdot (1 + \alpha))
~+ \sum_{v \notin m(v_1)} (1 + \mathrm{g}(v))
$$

A expressão m($v$), neste contexto, designa o conjunto dos vértices que pertencem ao mesmo módulo de $v$.

\end{subsection}

\begin{subsection}{O modelo LFR}

O modelo LFR \cite{Lancichinetti2008,Lancichinetti2009} é um modelo flexível que pode gerar redes com arestas ponderadas e módulos sobrepostos, isto é, nas quais um vértice pode pertencer a mais de um módulo. Diferentemente do CGW, o LFR não é um modelo de crescimento: todos os vértices são gerados de uma vez e então são adicionadas as arestas.

Nesta pesquisa foi estudado um caso particular do modelo no qual todas as arestas têm o mesmo peso e os módulos não se sobrepõem (cada vértice pertence a exatamente um módulo). O modelo aceita os seguintes parâmetros:

\begin{itemize}
\item número de vértices, $n$;
\item grau de entrada médio, $k$, com $k < n$;
\item grau de entrada máximo, $max_k$, com $k \le max_k < n$;
\item parâmetro de mistura, $\mu$, com $0 \le \mu \le 1$;
\item expoente da distribuição de graus, $-\gamma$;
\item expoente da distribuição de tamanho de módulos, $-\beta$;
\item tamanho do menor módulo, $min_m$;
\end{itemize}

Os tamanhos dos módulos são selecionados de uma lei de potência com expoente $-\beta$. O parâmetro de mistura, $\mu$, é a proporção de arestas externas na rede gerada. No modelo LFR, nem todas as combinações de parâmetros são factíveis. Por exemplo, se $n = 100$, então $min_m$ não pode ser 60, caso contrário existiriam módulos menores do que $min_m$.

\end{subsection}

\end{section}

\begin{section}{Conclusão} % síntese, súmula, resumo
	
	A teoria das redes complexas é uma área de pesquisa que oferece ferramentas teóricas as quais apoiam o estudo de redes do ponto de vista estatístico. A teoria tem sido aplicada no estudo de diversos domínios, como a sociologia, a biologia e a engenharia.
	
	Redes livres de escala são redes que possuem uma determinada distribuição de graus. Redes de dependências entre entidades de software já foram identificadas como redes livres de escala em diversos estudos recentes.
	
	Perfis de concentração de tríades (PCTs) caracterizam redes através de vetores de treze números. Dois PCTs podem ser comparados através do coeficiente de correlação de Pearson.
	
	ER, BA, CGW e LFR são modelos de redes. O modelo ER gera redes sem módulos que, em geral, não são livres de escala. O modelo BA gera redes não-orientadas, livres de escala e sem módulos. Os modelos CGW e LFR geram redes orientadas, livres de escala e organizadas em módulos.
	% TODO: E...?
	 % Com tais propriedades, essas redes podem representar dependências entre entidades de software.
		
\end{section}
